The problem can be found at the following link: Question Link
This is the standard Floyd-Warshall graph problem for finding the transitive closure of a graph.
- Initialize a transitive closure matrix with the given graph
- Set all diagonal elements to 1
- Use the Floyd-Warshall algorithm to compute the transitive closure by considering all pairs of vertices and updating the matrix based on the existence of a path between them through a third vertex.
For better understanding, refer to the following video: Floyd-Warshall Algorithm
- Time Complexity:
O(N^3)
, whereN
is the number of vertices in the graph - Auxiliary Space Complexity:
O(N^2)
is the number of vertices in the graph
class Solution {
public:
vector<vector<int>> transitiveClosure(int N, vector<vector<int>> graph)
{
vector<vector<int>> transitive(N, vector<int>(N, 0));
for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
{
transitive[i][j] = graph[i][j];
if (i == j)
{
transitive[i][j] = 1;
}
}
}
for (int k=0; k<N; k++)
{
for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
{
if (transitive[i][k] && transitive[k][j])
{
transitive[i][j] = 1;
}
}
}
}
return transitive;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.